package L612;

import util.TreeNode;

/**
 * @program: javase
 * @description:
 * @author: luolidong
 * @create: 2021-06-12 14:57
 * @version: 1.0
 */
public class Demo3 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 终止条件
        if(root==null||root==p||root==q) return root;
        // 后序遍历
        TreeNode left=lowestCommonAncestor(root.left,p,q);
        TreeNode right=lowestCommonAncestor(root.right,p,q);
        if(left==null) return right;
        if(right==null) return left;
        return root;
    }
    /**
     *            1
     *          / \
     *         2   3
     *        / \
     *       4   5
     **/
    public static void main(String[] args) {
        TreeNode t1 = new TreeNode(1);
        TreeNode t2 = new TreeNode(2);
        TreeNode t3 = new TreeNode(3);
        TreeNode t4 = new TreeNode(4);
        TreeNode t5 = new TreeNode(5);
        t1.left=t2;
        t1.right=t3;
        t2.left=t4;
        t2.right=t5;
        new Demo3().lowestCommonAncestor(t1, t3, t4);
    }
}
